package com.LeeCode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树的完全性检验
 */

public class Code958 {
    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, null, null, 15};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code958().isCompleteTree(root));
    }

    public boolean isCompleteTree(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        boolean flag = true;
        while (!deque.isEmpty()) {
            TreeNode node = deque.poll();
            if (node == null) {
                flag = false;
            } else {
                // 如果在非空节点前出现了空节点那么则为false
                if (!flag) {
                    return false;
                }
                deque.offer(node.left);
                deque.offer(node.right);
            }
        }
        return true;
    }

}
